class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int dir[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
        int res = 0;
        int n = grid.size();
        int x,y,i;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        vector<vector<int>> dis(grid.size(), vector<int>(grid.size(), -1));
        queue<pair<int,int>> que;
        que.push({0,0});
        visited[0][0] = true;
        dis[0][0] = 0;
        if (grid[0][0] == 1)
        {
            return -1;
        }
        while (!que.empty())
        {
             x = que.front().first;
             y = que.front().second;
            que.pop();
            for ( i=0; i < 8; i++)
            {
                int newX = x+dir[i][0];
                int newY = y+dir[i][1];
                if (newX >= 0 && newX < n && newY >= 0 && newY< n && !visited[newX][newY] && !grid[newX][newY])
                {
                    dis[newX][newY] = dis[x][y]+1;
                    visited[newX][newY] = true;
                    que.push({newX, newY});
                }
            }
        }
        return dis[n-1][n-1] == -1? -1:dis[n-1][n-1]+1;
    }
};